In general, wireless networks, such as cellular telephone systems, may be arranged in a two-tier architecture. The first tier typically includes clusters or cells, each including communication nodes or cluster members. One node within each cluster is designated a cluster head or base station. The second tier includes a backbone network formed of the cluster head nodes to enable communications between different clusters. The formation of clusters and designation of cluster head nodes is generally performed dynamically and in accordance with an intranet protocol (e.g., a protocol for communications within the two-tier network) that further performs routing functions within the network. The intranet protocol may be a link-state type of routing protocol that is implemented on the backbone network. The cluster head nodes each include a database that is synchronized with other head node databases by transference of link-state advertisement (LSA) packets in accordance with the protocol. These databases include information enabling the cluster head nodes to determine appropriate paths for routing messages thorough the network, while the LSA packets provide information to update the databases.
For routing in mobile ad hoc networks, general purpose routing schemes, such as distance-vector (DV) and link-state (LS), distribute routing information to communication peers within the network. The amount of flooding overhead for the dissemination of routing information by these routing approaches is generally influenced by two key factors, namely, network size and volatility of network connectivity. The amount of flooding overhead usually increases, when the network size increases and/or the underlying network becomes more volatile.
To reliably disseminate routing information, conventional DV and LS protocols deploy a two-way exchange scheme. When a communication node running the DV or LS protocol needs to distribute a piece of routing information to its routing neighbor(s), it sends a point-to-point packet to the neighbor. Upon reception of the routing packet, the routing neighbor returns an acknowledgment packet back to the sender of the routing packet. When it has two or more routing neighbors, instead of sending separate point-to-point routing packets to each routing neighbor, the communication node sends one broadcast routing packet to all the routing neighbors, which return point-to-point acknowledgment packets back to the communication no made after the routing packet is received.
The amount of flooding overhead, generally, increases exponentially faster than the increase of network size. In fact, the amount of flooding overhead generated by these conventional approaches is manageable only for small scale networks (<30 communication nodes). For large scale networks, the amount of flooding overhead tends to overwhelm the network and result in network communication breakdown. In addition, volatile network connectivity tends to introduce more changes in network link metrics, which in turn causes more routing information to be distributed in the network.
U.S. Pat. No. 6,385,174, issued to one of the inventors of the present invention, on May 7, 2002, discloses a method of transmitting LSA packets or messages within a wireless communication system. The method utilizes a version of an open shortest path first (OSPF) routing protocol or a radio open shortest path first (ROSP) routing protocol. This patent is incorporated herein by reference in its entirety.
As described in the patent, ROSPF LSA type packets are transmitted to neighbors of each node to enable each database to maintain current information. In order to reduce overhead of transmitting numerous LSA type packets, ROSPF LSA type packets are transmitted within an intranet protocol that is periodically broadcasted within the network. In this manner, the increase in overhead flooding rate is reduced.
Although the flooding overhead is reduced using the system described in the patent, nevertheless, as the number of nodes increases in a network, the amount of flooding overhead increases exponentially. Because the amount of flooding overhead generated by conventional flooding approaches increases exponentially faster than the underlying network size, traditional approaches are only workable in smaller scale networks, with relative stable network connectivity. For larger scale and/or more volatile networks, conventional approaches tend to generate too much flooding overhead that shuts down communication in the underlying network.
What is needed is a system and method that disseminates routing information that further eliminates redundant flooding of information. The present invention addresses this need.